package com.gxc.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符串的子序列
 */
public class SubSequence {

    public static void main(String[] args) {
        String str = "abc";
        String result = "";
        subSequence(result, 0, str.toCharArray());
        System.out.println("---------");
        List<Character> list = new ArrayList<>();
        subSequence(list, 0, str.toCharArray());

        System.out.println("---------");
        subSequence(0, str.toCharArray());
    }

    /**
     * 不用额外空间
     * @param n
     * @param chars
     */
    public static void subSequence(int n, char[] chars) {
        if (n == chars.length) {
            System.out.println(String.valueOf(chars));
            return;
        }
        //要n位置的字符
        subSequence(n+1, chars);
        //不要n位置的字符
        char temp = chars[n];
        chars[n] = 0;
        subSequence(n+1, chars);
        //还原
        chars[n] = temp;
    }

    public static void subSequence(List<Character> list, int n, char[] chars) {
        if (n == chars.length) {
            printList(list);
            return;
        }
        char c = chars[n];
        //不要n位置的字符
        List<Character> noIncludeLIst = copyLIst(list);
        subSequence(noIncludeLIst, n+1, chars);
        //要n位置的字符
        List<Character> includeLIst = copyLIst(list);
        includeLIst.add(c);
        subSequence(includeLIst, n+1, chars);
    }

    private static List<Character> copyLIst(List<Character> list) {
        List<Character> result = new ArrayList<>();
        for (Character character : list) {
            result.add(character);
        }
        return result;
    }

    private static void printList(List<Character> list) {
        for (Character character : list) {
            System.out.print(character);
        }
        System.out.println("");
    }

    public static void subSequence(String str, int n, char[] chars) {
        if (n == chars.length) {
            System.out.println(str);
            return;
        }
        char c = chars[n];
        //不要n位置的字符
        subSequence(str, n+1, chars);
        //要n位置的字符
        subSequence(str+c, n+1, chars);
    }

}
